The present invention concerns the automatic synthesis of large scale integrated circuits (usually called "very large" scale integrated circuits) with the aid of a programmed machine, usually called a compiler, by means of which an operator initially specifies a complex digital processing function and achieves a detailed instruction for the layout of a very large scale integrated circuit which implements, in a selected technical realization (such as CMOS circuits) the complex function which has been specified by the operator. The design, checking and testing of such integrated circuits is so complex that the use of automatic synthesis using a programmed machine is essential for the task. This is partly because the digital signal processing functions are inherently complicated, partly because the main data processing functions need to be decomposed into simpler functions which are within the "library" of circuits to which the compiler has access, and partly because considerable computation is required in order to achieve an efficient layout of the network. It will be understood that the result of the computerised design process is a detailed specification defining, in terms of a particular technology, a complex integrated circuit.
Algorithms for use in automatic synthesizers and compilers are commercially known and are extensively described in the technical literature.
Automatic logic synthesis of very large scale integrated circuits requires several operations to transform a high level description into a physically realizable design. The process typically commences with the original functional statement of the circuit or processor which is to be synthesized and follows with the stages of minimization, factorization and mapping. The last mentioned stage is a synthesis in terms of the basic circuits or cells which are maintained for access in a cell library. Before this stage is implemented the circuit or processor which is to be synthesized is expressed in terms of logic, such as Boolean equations, in a manner which is independent of technology. Such a manner of expression does not express the logic in terms of particular circuits which are dependent upon the choice of fabrication. The mapping process converts the logical representation which is independent of technology into a form which is dependent on the selected technology and has recourse, as previously mentioned, to standard circuits or cells which are held within a cell library forming part of the data available to the compiler.
The original functional statement in terms of Boolean logic equations is normally very complex and is far from optimal in terms of area or delay.
Considerable attention has therefore been devoted in recent years to the development of algorithms for the minimization and decomposition of logical functions into multi-level logic which can more efficiently realise the desired function. Its final quality is measured in terms of area, delay or a compromise of these criteria.